// 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
// 示例 1:
// 输入: [0,1,3]
// 输出: 2
// 示例 2:
// 输入: [0,1,2,3,4,5,6,7,9]
// 输出: 8
// 限制：
// 1 <= 数组长度 <= 10000

// ①暴力循环
var missingNumber = function(nums) {
    let len = nums.length;
    if(len < 1 || len > 10000) return len;
    
    for(let i=0;i<=len;i++) {
        if(i !== nums[i]) {
            return i;
        }
    }
    
    return len;
};

// 二分法
var missingNumber2 = function(nums) {
    let left = 0,
        right = nums.length -1;
        
    while(left <= right) {
        let mid = Math.floor((left + right)/2);
        // 如果mid等于nums[mid]，说明没找到，前半段也是按顺序的，所以取右区间
        if(mid === nums[mid]) {
            left = mid+1;
        }else if(mid < nums[mid]) {
            // 如果mid不等于nums[mid]，并且mid值小于nums[mid]，说明空缺值在左区间
            right = mid-1;
        }
    }
    
    return left;
};
